정보과학회논문지 (Journal of KIISE)
Current Result Document :
| 한글제목(Korean Title) |
배낭 문제를 이용한 조합경매의 승자 결정 |
| 영문제목(English Title) |
Winner Determination of Combinatorial Auction Using the Knapsack Problem |
| 저자(Author) |
공은배
Eun Bae Kong
|
| 원문수록처(Citation) |
VOL 47 NO. 07 PP. 0629 ~ 0634 (2020. 07) |
한글내용
(Korean Abstract) |
조합경매는 상품들의 조합에 입찰을 할 수 있게 한다. 상품간에 상호 보완성이 있는 경우 상품들의 가치를 정확하게 표현할 수 있게 하여 거래와 시장의 효율을 높일 수 있는 중요한 기술이다. 조합경매의 승자 결정 문제(WDP)는 NP-완전 문제로 해결하기 매우 어렵지만 현실적으로 많은 분야에 응용될 수 있는 매우 중요한 문제이다. 본 논문에서는 WDP를 배낭 문제를 이용하여 마코프 체인 몬테 칼로 방식을 적용하여 해를 구하는 방안을 제시하였다. 정수계획법과의 비교 실험을 통해 해의 성능이 정수계획법에 의한 해에 필적하는 것을 확인하였다.
|
영문내용
(English Abstract) |
In combinatorial auctions, bidders can make bids on a set of items. When the items show complementarities in values, combinatorial auctions make it possible to express the values more accurately and enhance the market’s efficiency. The winner determination problem is an NP-complete problem. To address this difficult and important problem, we can attempt to solve the special subproblem that can be solved efficiently or develop approximate solutions. In this paper, we reformulated the WDP into a knapsack problem. By using Markov chain Monte Carlo method, we achieved a desired stationary solution with a large objective function. The solution is comparable to that of integer programming
|
| 키워드(Keyword) |
조합경매
승자 결정
배낭 문제
마코프 체인 몬테 칼로
combinatorial auctions
winner determination
knapsack problem
Markov chain Monte Carlo
|
| 파일첨부 |
PDF 다운로드
|
